package Leetcode100Hot;

import org.junit.Test;

import java.util.*;

/*
最长有效括号
给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

示例 1：
输入：s = "(()"
输出：2
解释：最长有效括号子串是 "()"
示例 2：
输入：s = ")()())"
输出：4
解释：最长有效括号子串是 "()()"
示例 3：
输入：s = ""
输出：0

提示：
0 <= s.length <= 3 * 104
s[i] 为 '(' 或 ')'
 */
public class _60最长有效括号 {

    @Test
    public void test() {
        System.out.println(longestValidParentheses("()()"));
    }

    //栈   WA        156/231
    //ps: WA原因：计数方式不行
    // 可以采用下标减法计数
    public int longestValidParentheses(String s) {
        Map<Character,Character> map = new HashMap<>(){{
            put(')','(');
        }};
        Deque<Character> stack = new ArrayDeque<>();
        char[] charArray = s.toCharArray();
        int count = 0;
        int res = 0;
        for (int i = 0; i < charArray.length; i++) {
            char c = charArray[i];
            if (map.containsKey(c)) {
                if (stack.isEmpty() || stack.peek() != map.get(c)) {
                    count = 0;
                }else {
                    count++;
                    stack.pop();
                    res = Math.max(res, count * 2);
                }
            }else {
                stack.push(c);
            }
        }
        return res;
    }

    //方法一：动态规划
    /*
    1.定义状态
    我们定义 dp[i] 表示以下标 i 字符结尾的最长有效括号的长度。(重点有效括号)
    2.边界状态
    显然有效的子串一定以 ‘)’ 结尾
    3.状态方程
    s[i]=‘)’ 且 s[i−1]=‘(’
        dp[i]=dp[i−2]+2
    s[i]=‘)’ 且 s[i−1]=‘)’，也就是字符串形如 “……))”，我们可以推出：
        如果 s[i−dp[i−1]−1]=‘(’   dp[i]=dp[i−1]+dp[i−dp[i−1]−2]+2
        否则 dp[i] = 0;
    */
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/longest-valid-parentheses/solutions/314683/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
     */
    class Solution {
        public int longestValidParentheses(String s) {
            int maxans = 0;
            int[] dp = new int[s.length()];
            for (int i = 1; i < s.length(); i++) {
                if (s.charAt(i) == ')') {
                    if (s.charAt(i - 1) == '(') {
                        dp[i] = (i >= 2 ? dp[i - 2] : 0) + 2;
                    } else if (i - dp[i - 1] > 0 && s.charAt(i - dp[i - 1] - 1) == '(') {
                        dp[i] = dp[i - 1] + ((i - dp[i - 1]) >= 2 ? dp[i - dp[i - 1] - 2] : 0) + 2;
                    }
                    maxans = Math.max(maxans, dp[i]);
                }
            }
            return maxans;
        }
    }

    //官解：方法二：栈
    //ps: 栈放入左括号的下标，通过下标相减计数
    //ps: 维护最后一个没有被匹配的右括号的下标，来处理边界问题
    /*
    作者：力扣官方题解
    链接：https://leetcode.cn/problems/longest-valid-parentheses/solutions/314683/zui-chang-you-xiao-gua-hao-by-leetcode-solution/
     */
    class Solution2 {
        public int longestValidParentheses(String s) {
            int maxans = 0;
            Deque<Integer> stack = new LinkedList<Integer>();
            stack.push(-1);
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    stack.push(i);
                } else {
                    stack.pop();
                    if (stack.isEmpty()) {
                        stack.push(i);
                    } else {
                        maxans = Math.max(maxans, i - stack.peek());
                    }
                }
            }
            return maxans;
        }
    }

}
